package com.learn.finished;
/*
剑指 Offer 24. 反转链表

定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

 */

public class num_offer_24 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode prev = null, next;
        ListNode curr = head;
        //原来的头结点是尾结点，必定指向null，后一个会指向前一个，即second应该指向head。
        // 那么second.next应该指向的是second，但是如果second.next提前指向了second
        //会导致原有的链表丢失。所以在此期间应该用一个tmp存储链表的信息
        while (curr != null) {
            //保存指针
            next = curr.next;
            //要设置对比链表的next
            curr.next = prev;
            prev = curr;
            curr = next;

        }
        return prev;
    }

    public static ListNode recursionReverseList(ListNode head) {
        //如果传入的链表为空，或者长度为1，即没有判断必要，直接返回即可
        if (head == null || head.next == null) {
            return head;
        }
        //此处运用递归的方法，先找到最后一个，然后再从尾进行排序
        ListNode newHead = recursionReverseList(head.next);
        //此处返回的newHead是原链表中的最后一个，那么，在此处，head.next，即为最后一个的前一个
        //此处进行绑定，将后面接到前面，然后将最后一个置空
        head.next.next = head;
        head.next = null;
        //将处理好的头结点返回
        return newHead;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(5);
        ListNode listNode2 = new ListNode(10);
        ListNode listNode3 = new ListNode(7);
        ListNode listNode4 = new ListNode(8);
        ListNode listNode5 = new ListNode(9);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        ListNode listNode = reverseList(listNode1);
        System.out.println(listNode);

    }
}
